1. Field of the Invention
The present invention relates to a hierarchical network with a reduced number of internode paths and a multiprocessor system utilizing the same.
2. Description of the Related Art
Investigation has hitherto been made on a network for coupling a plurality of nodes, and a variety of networks have been devised. These node coupling system are introduced in an explanation article "Coupling System" by Kyoichi Kurokawa et al. (Information Processing, vol. 27, No. 9, Sep. 1989, pp. 1005-1021). In this explanation, networks are classified into "dynamic" networks and "static" networks depending on whether or not coupling between input and output dynamically changes. The dynamic networks include a crossbar network, a baseline network, an omega network, a butterfly network (indirect n-cube), a delta network, Banyan network and so on. On the other hand, the static networks include a ring network, a star network, a tree network, a lattice network, a perfect coupling network, an n-cube, a CCC (Cube Connected Cycle) and so on.
In the field of computer architecture, a variety of multiprocessor systems have been investigated and developed applying the above-mentioned networks. Typical one of these multiprocessor systems may be TC2000 (by BBN in USA) utilizing a butterfly network described in an article "BBN TC2000 Architecture and Programming Models" by E. D. Brocks et al (Porc. of COMPCON '91, pp. 46-50, 1991). Also given as an example is a multiprocessor system utilizing a tree network called a duplexed Ynet which is described in JP-A-57-101931. In recent years, a hypercube (n-cube) type network is particularly drawing attention, and nCUBE (by nCUBE in USA) and iPSC (by Intel in USA) have been developed as multiprocessors to which this type of network is applied.
As stated above, the hypercube has become one of leading multiprocessor systems. Also, as a concept covering the majority of the static network, there is k-array n-cube (J. DALLY, "Performance Analysis of k-array n-cube Interconnection Network", Trans. on Computers, vol. 39, No. 6, JUNE 1990). Not only the hypercube but also the ring network, lattice network, torus network, omega network, indirect n-cube and so on are all specialized versions of this k-array n-cube or a similar type of networks thereto.
A hypercube configuring a prior art network will be briefly explained with reference to FIGS. 1A-1E. FIGS. 1A-1E illustrate two-dimensional, three-dimensional, four-dimensional and five-dimensional hypercubes, respectively. The number of nodes N and the number of internode connection buses from one node M are set to N=2 and M=2 in the one-dimensional hypercube; N=4 and M=2 in the two-dimensional hypercube; N=8 and M=3 in the three-dimensional hypercube; N=16 and M=4 in the four-dimensional hypercube; N=32 and M=5 in the five-dimensional hypercube; and N=2 n (an operator " " represents a power) and M=n in an n-dimensional hypercube. In the prior art hypercube, as the number of nodes N is increased, the number of internode connection buses MM is also increased. For example, in a hypercube having the number of nodes equal to N=2 n, MM=(Nlog.sub.2 N)/2. For example, in the one-dimensional hypercube shown in FIG. 1A, since N=2, MM=(2log.sub.2 2)/2=1; in the two-dimensional hypercube shown in FIG. 1B, since N=8, MM=(8log.sub.2 8)/2=12; and when the number of nodes N is equal to 2 16, MM=524,288. Thus, as the number of nodes is increased, the resulting number of internode connection buses becomes immense. For this reason, it is practically difficult to configure a multiprocessor system utilizing this network so as to allocate a processor to each node.
To solve this problem, the foregoing CCC network or the like has been devised which forms a ring with nodes located at respective peaks of a hypercube (described in the foregoing explanation article, p1027). However, this network has a drawback that an internode transfer distance becomes longer than another type of hypercube having a similar number of nodes depending on the positions of nodes. Although a tree network, which is a hierarchical network described in the foregoing explanation article, p1014, can reduce the number of internode connection buses, it has a drawback that the internode transfer distance becomes longer, similarly to the CCC. For example, in an n-stage binary tree network having the number of nodes equal to (2 n)-1, the internode transfer distance is doubled as compared with an n-dimensional hypercube having the substantially same number of nodes. In a multiprocessor system, an interprocessor communication time is very important. The interprocessor communication time generally increases in proportion to the distance of an internode transfer path. In a hypercube network, assuming that the number of node N is equal to 2 n (N=2 n), a maximum value Dmax of the internode transfer distance is expressed by Dmax=log.sub.2 N. For example, in a system having the number of nodes equal to 2 16 (N=2 16), its maximum transfer distance is 16 (Dmax=16).
A multiprocessor utilizing a hypercube network also has a problem in the expansibility. Specifically, if a processor is added to an arbitrary hypercube system, existing processors must be additionally provided with a network connection port corresponding to the added processor. It is therefore impossible to practically add processors more than the previously designed number of ports.
Further, in a tree network, since a transfer path is uniquely determined, communication paths frequently fall into a closed stage, thereby hindering a parallel transfer of data.
In addition, for building a large scale multiprocessor system employing a plurality of one module/chip multiprocessor systems in which a plurality of processors are mounted on a single module or LSI chip, the following problems may arise. Assume, for example, that a multiprocessor system comprising 2 16 units of processors is realized by applying a plurality of one-chip multiprocessors containing, for example, 128 (=2 7) processors to a hypercube network. If 2 9 units of the chips are used to build a 16-dimensional hypercube system, the number of internode connection buses equal to 1,152 must be drawn from one chip, which apparently results difficulties in providing the chip with such a large number of pins. Such a situation presents a more grave problem as the number of used processors and accordingly the scale of a built system are increased.